// greedy alg.
// traverse s twice.
// First, acquire map, key is char, value is last appearence index;
// Second, [start, end], end=max(end, endC), C is current char;
// Meanwhile, record (end-start+1) to length array;
// time: O(2n)即O(n), space: <=O(26)即O(1)
func partitionLabels(s string) []int {
	m := make(map[rune]int)
	for i, r := range s {
		m[r] = i
	}

	var res []int
	start, end := 0, 0
	for i, r := range s {
		end = max(end, m[r])
		if i == end {
			res = append(res, end-start+1)
			start, end = i+1, i+1
		}
	}

	return res
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}